package 递归回溯;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class No78子集 {

    /**
     * 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
     * 说明：解集不能包含重复的子集。
     *
     * 示例:
     * 输入: nums = [1,2,3]
     * 输出:
     * [
     *   [3],
     *   [1],
     *   [2],
     *   [1,2,3],
     *   [1,3],
     *   [2,3],
     *   [1,2],
     *   []
     * ]
     */

    private int[] arr;
    private List<List<Integer>> lists=new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        Deque<Integer> path=new ArrayDeque<>();
        this.arr=nums;
        dg(path,0);
        return lists;
    }

    private void dg(Deque<Integer> path,int start){
        if(path.size()==arr.length){
            lists.add(new ArrayList<>(path));
            return;
        }
        lists.add(new ArrayList<>(path));

        for (int i = start; i < arr.length; i++) {
            path.addLast(arr[i]);
            dg(path,i+1);
            path.removeLast();
        }
    }

}
